class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> dp(n + 1, INT_MAX);
        int durings[3] = { 1, 7, 30 };
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i, k = 0; k < 3; k++)
            {
                while (j < days.size() && days[i] + durings[k] > days[j])
                    j++;
                dp[i] = min(costs[k] + dp[j], dp[i]);
            }
        }
        return dp[0];
    }
};